// 版权2019 etcd作者
// 
// 根据Apache许可证2.0版（以下简称“许可证”）获得许可；
// 除非遵守许可证，否则不得使用此文件。
// 您可以通过
// 
// www.apache.org/licenses/LICENSE-2.0 
// 
// 除非适用法律要求或书面同意，否则根据许可证分发的软件
// 按“原样”分发，
// 无任何明示或暗示的保证或条件。
// 请参阅许可证，了解管理许可的特定语言和
// 许可证下的限制。

package quorum

import (
	"fmt"
	"math"
	"sort"
	"strings"
)

// MajorityConfig是一组ID，它使用多数配额来做出决策。
type MajorityConfig map[uint64]struct{}

func (c MajorityConfig) String() string {
	sl := make([]uint64, 0, len(c))
	for id := range c {
		sl = append(sl, id)
	}
	sort.Slice(sl, func(i, j int) bool { return sl[i] < sl[j] })
	var buf strings.Builder
	buf.WriteByte('(')
	for i := range sl {
		if i > 0 {
			buf.WriteByte(' ')
		}
		fmt.Fprint(&buf, sl[i])
	}
	buf.WriteByte(')')
	return buf.String()
}

// descripe返回给定lookuper的提交索引的（多行）表示形式。
func (c MajorityConfig) Describe(l AckedIndexer) string {
	if len(c) == 0 {
		return "<empty majority quorum>"
	}
	type tup struct {
		id  uint64
		idx Index
		ok  bool // 找到idx了吗？
		bar int  // 为该tup显示的条形图长度
	}

	// 如下，填充。这样第i个最大的提交索引就有了条i（我们
	// 将其绘制为一种进度条）。实际代码有点复杂，并且确保了equal index=>equal bar。

	n := len(c)
	info := make([]tup, 0, n)
	for id := range c {
		idx, ok := l.AckedIndex(id)
		info = append(info, tup{id: id, idx: idx, ok: ok})
	}

	// 按索引排序
	sort.Slice(info, func(i, j int) bool {
		if info[i].idx == info[j].idx {
			return info[i].id < info[j].id
		}
		return info[i].idx < info[j].idx
	})

	// 填充。酒吧
	for i := range info {
		if i > 0 && info[i-1].idx < info[i].idx {
			info[i].bar = i
		}
	}

	// 按ID排序。
	sort.Slice(info, func(i, j int) bool {
		return info[i].id < info[j].id
	})

	var buf strings.Builder

	// 打印。
	fmt.Fprint(&buf, strings.Repeat(" ", n)+"    idx\n")
	for i := range info {
		bar := info[i].bar
		if !info[i].ok {
			fmt.Fprint(&buf, "?"+strings.Repeat(" ", n))
		} else {
			fmt.Fprint(&buf, strings.Repeat("x", bar)+">"+strings.Repeat(" ", n-bar))
		}
		fmt.Fprintf(&buf, " %5d    (id=%d)\n", info[i].idx, info[i].id)
	}
	return buf.String()
}

// Slice将多数配置作为已排序的切片返回。
func (c MajorityConfig) Slice() []uint64 {
	var sl []uint64
	for id := range c {
		sl = append(sl, id)
	}
	sort.Slice(sl, func(i, j int) bool { return sl[i] < sl[j] })
	return sl
}

func insertionSort(sl []uint64) {
	a, b := 0, len(sl)
	for i := a + 1; i < b; i++ {
		for j := i; j > a && sl[j] < sl[j-1]; j-- {
			sl[j], sl[j-1] = sl[j-1], sl[j]
		}
	}
}

// CommittedIndex根据通过
// 提供的AckedIndex（用于活动配置）提供的索引计算提交的索引。
func (c MajorityConfig) CommittedIndex(l AckedIndexer) Index {
	n := len(c)
	if n == 0 {
		// 这与联合配额很好，当一半为零
		// 多数配置时，其行为应与另一半相同。
		return math.MaxUint64
	}

	// 当n<=7 
	// 时，使用堆栈上的切片来收集提交的索引（否则我们分配）。另一种选择是在
	// MajorityConfig上隐藏一个切片，但这会影响可用性（就像，MajorityConfig只是一个地图，这很好）。假设在
	// 复制因子大于7的情况下运行是很少见的，并且在这种情况下，
	// 性能是一个较小的问题（此外，这里分配的性能
	// 影响远不是很大）。
	var stk [7]uint64
	var srt []uint64
	if len(stk) >= n {
		srt = stk[:n]
	} else {
		srt = make([]uint64, n)
	}

	{
		// 用观察到的索引填充切片。任何未使用的插槽将被
		// 保留为零；这些都对应于可能会报到的选民，但
		// 尚未报到。我们从右边填充（因为在下面进行排序后，零将在
		// 左边结束）。
		i := n - 1
		for id := range c {
			if idx, ok := l.AckedIndex(id); ok {
				srt[i] = uint64(idx)
				i--
			}
		}
	}

	// 按索引排序。使用定制算法（从stdlib的sort 
	// 包复制）将srt保留在堆栈上。
	insertionSort(srt)

	// 数组中的最小索引，其值由
	// 仲裁确认。换句话说，从切片的末尾，将n/2+1移动到
	// 左侧（考虑零索引）。
	pos := n - (n/2 + 1)
	return Index(srt[pos])
}

// VoteResult获取选民到是/否（真/假）选票的映射，并返回
// 结果，表明投票是否悬而未决（即未达到法定人数
// 是/否）、获胜（达到法定人数是）或失败（达到法定人数否）。
func (c MajorityConfig) VoteResult(votes map[uint64]bool) VoteResult {
	if len(c) == 0 {
		// 按照惯例，空位上的选举获胜。这在
		// 联合定额中很方便，因为它将使半填充的联合
		// 定额表现为多数法定人数。
		return VoteWon
	}

	ny := [2]int{} // 分别计算反对票和赞成票

	var missing int
	for id := range c {
		v, ok := votes[id]
		if !ok {
			missing++
			continue
		}
		if v {
			ny[1]++
		} else {
			ny[0]++
		}
	}

	q := len(c)/2 + 1
	if ny[1] >= q {
		return VoteWon
	}
	if ny[1]+missing >= q {
		return VotePending
	}
	return VoteLost
}
